1. Technical Field
The invention relates to logic design automation and more particularly to logic synthesis.
2. Glossary of Terms
A Box is the single organizational component of a logic synthesis database. It has input and output terminals, which allow connection to other boxes by nets. Each box is designated by a type, which may be a primitive or may reference a definition in terms of other boxes. Thus, a hierarchy of boxes can be used and an instance of a high-level box type, such as a parity box, may be treated as a single box or expanded. A block is equivalent to a box.
A Component Instantiation implies a block of hierarchy within a design entity containing a unique instance of another section of design defined by another design entity. In VHDL, a component instantiation statement and corresponding specification may be used to define the instance of a gate from a technology library and identify its connections, respectively.
Control Logic tends to be characterized by complex, unpredictable interrelationships of signals. Such logic usually contains a large amount of redundancy, which decreases testability, requires more connections than necessary, increases area and produces long and slow paths.
A Covering Algorithm, sometimes called mapping or technology mapping, is the implementation of a generic Boolean network using a library of technology dependent gates.
Data Flow Logic is characterized by highly parallel and well-known or well-understood combinatorial algorithms, such as adders and multipliers, and may include the most critical timing path for the design.
Expressions are the product of parsing register transfer level statements. They correspond one for one with source level statements and are stored as a string of tokens on a box. They are in prefix form (postfix form would be equivalent), i.e. in the string form of a parse tree. They are commonly vectored and are made of n-ary operators.
Logic Synthesis is used to mean the synthesis of a technology dependent model from a register transfer level description.
A Netlist is a detailed interconnection listing of boxes in the target technology from which automated logic diagrams may be produced for integrated circuit fabrication.
Primitives are technology independent gates, e.g. AND gates, ORs, NOTs, etc.
A Register Transfer Level Description is a high level abstraction of a logic design. It comprises logic functions to be implemented in an integrated circuit. Interface constraints and a technology database may be specified. An example of a language that may be used for RTL description is VHDL.
Structural Dominance is a tool taught by the present invention allowing a logic designer to imply structure in a source language at the Register Transfer Level, which structure may be preserved through synthesis out to a resulting logic design.
Transformation is a term for a collection or suite of programs which operate on expressions or manipulate boxes representing boolean functions and their connections.
3. Description of the Related Art
The design of very large scale integration (VLSI) circuits presents a number of challenges beyond those encountered in the design and development of smaller integrated circuit chips. A longer manufacturing cycle, tighter timing requirements, shorter machine cycle, and a larger number of gates per designer all must be overcome while meeting a short development time budget.
Logic synthesis is a process used to convert a technology independent logic description into a netlist which may be directly implemented in a technology and thereby speed circuit development. Logic synthesis addresses many problems, one of them being the conversion of a more-or-less technology independent register transfer level (RTL) design model to a technology dependent model. Computer programs that perform logic synthesis are known, however these computer programs generally use mathematical techniques that do not have general solutions. Faced with the lack of a rigorous mathematical solution, logic design engineers have had to develop techniques which may not be mathematically rigorous but which do produce acceptable results. Such techniques generally involve compromises and practical limitations. Logic synthesis can also be used to generate a technology dependent model from a very high level (e.g. higher than RTL) description or to convert a technology dependent design to a different technology.
Prior art logic synthesis programs generally operate as follows. The logic synthesis program begins by having the designer describe the desired logic function in a "register transfer level description." The set of register transfer level expressions are then parsed into tokens. Next these tokens are converted to a set of primitive boolean function boxes. Logic reduction transformations are then performed on this global set of primitive boxes.
One problem encountered while synthesizing a design is providing the same level of information to the logic synthesis system as would be available to a human designer. Much of the information available to a designer, however, does not exist in any computer-readable form. Yet, a Register Transfer description contains a great deal of information in the form of the logic structure which could be used by the logic synthesis tool.
Typically, as the RTL description is processed in preparation for logic synthesis, the model is reduced to primitive form, thus destroying most of the structural information contained in the original description. This is done to place fewer restrictions on the logic reduction programs. However, experiments have shown that structural restrictions based on external broad-based knowledge (i.e. global information possessed by the designer and injected into the synthesis system via structure) produce better results.
Compounding the problem of structural information loss, RTL languages are often degraded to a very primitive dyadic form making preservation of the structural information more difficult than for other description forms (graphics descriptions, for example). U.S. Pat. No. 5,029,102 teaches techniques for processing the output of a parser prior to and during the logic synthesis process which have made it possible to preserve the designers original structure to a very large extent. One of the primary benefits this provides is that changes to the synthesized design may be effected in a predictable manner by modifying the original register transfer level description.
What constitutes optimality is not directly quantifiable. An "optimal" logic design for one technology is frequently not an "optimal" design in another technology. Indeed what is optimal in one technology may depend upon the particular application, or overall design, rather than local improvement. However, several factors are generally agreed as being suitable for grading the results of a logic synthesis process. These are: (1) the area of the design (essentially the number of cells or gates); (2) the wireability of the design (related to the number of connections); (3) the timing of the design; and (4) the testability of the design. While all of the above factors affect the perceived quality of the design, they also produce conflicting requirements for the synthesis tool.
Logic synthesis has been perceived as being advantageously applied to control logic portions of a design but not for data flow portions. Designers continue to manually tune data flow logic at a detailed level as a result of designer reluctance to accept the results of the logic synthesis tool. The reason for a distinction between control logic design and data flow logic design is related to distinct properties of these classes and the manner in which they are designed.
In control logic the interrelationship of signals tends to be complex, unpredictable and therefore difficult to optimize manually. Such logic usually contains a large amount of redundancy which decreases testability, requires more connections than necessary, increases area and produces long and slow paths.
Data flow logic designs tend to be highly parallel and usually embody well-known or well-understood combinatorial algorithms such as adders and multipliers. Also, data flow logic often becomes the centerpiece of a design and may contain the most critical timing path for the design. Thus, the designer usually carefully considers the design and typically desires a great deal of control over implementation.
The designer preference for control or determinism in data flow logic may be seen as having driven logic synthesis research toward automation of control logic synthesis. Synthesis systems generally destroy any original structure implied in the RTL description of the design. Determinism and optimization have been generally seen as incompatible. However, J. Bendas, in an article titled "Design Through Transformation", in Proceedings of the 20th ACM/IEEE Design Automation Conference, pp. 253-256, June 1983, suggested adding determinism of structure to synthesis. This was accomplished by taking advantage of the fact that synthesis processes generally operate on primitives. Transformation programs which had the most effect on logic structure were bounded, letting only some operations touch basic structural elements, e.g. AND-OR boxes. The results improved mapping because of the increased flexibility given the designer. The structure coming into synthesis was generally being produced by synthesis. The designer gained control over the result not provided by pure synthesis. The approach worked well for some logic. The improved synthesis of dataflow logic frequently proved worth the cost of some loss of optimization of control logic that resulted.
U.S. Pat. No. 5,029,102 also describes a logic synthesis system which operates on a set of register transfer statements describing the desired logic. The statements are parsed to allow logic reduction to be applied on the individual expressions. The expressions as modified by the reduction operation are converted to a set of technology independent boxes (TIBs), representing common boolean functions, such as AND, OR, AND-OR, etc. Logic reduction is then performed on the global set of any remaining primitives.
U.S. Pat. No. 5,029,102 further provides for the manipulation and optimization of expressions contained within boxes. Such expression processing or transformation is used to simplify traversing or changing the expressions. The various operations which may be performed on an expression include: (1) conversion of dyadic operators into n-adic; (2) changing negation operators to their complement; (3) DeMorgan related optimization; (4) Two level function recognition; and (5) Expansions to "normal" logic primitives. Operations are performed on the expressions but not between expression boxes. Expressions are then expanded into TIBs for further synthesis operations.
In order for logic synthesis to reduce the logic design cycle time, it must be applied to all aspects of design, not just control logic. While simple mapping tools and improved design entry tools, for example schematic capture, can reduce the time for a designer to enter or change a low level design, there remains a significant amount of effort for designers using such tools and they do not bring all of the possible advantages of applying logic synthesis to all aspects of a design problem.
U.S. Pat. No. 5,029,102 provides more control to the designer while allowing the tool some flexibility in its implementation of the design. This overcomes some designer reluctance to apply logic synthesis to data flow logic design.
However, it is desirable to give still more control to the designer over the results of synthesis. At the same time logic synthesis is given some freedom to optimize results where structural control is used. Finally, the designer should be able to mix tight control, loose control and unencumbered logic synthesis over different parts of an implementation.